package entity

import "cmp"

/*
BstSearch
最坏情况下时间复杂度为 O(log2 N)
最坏情况下时间复杂度为 O(N)
*/
func (n *PNode[T]) BstSearch(root *PNode[T], val T) *PNode[T] {
	if root == nil {
		return nil
	}
	switch val {
	case root.Data:
		return root
	default:
		if cmp.Less(val, root.Data) {
			return n.BstSearch(root.Left, val)
		} else {
			return n.BstSearch(root.Right, val)
		}
	}
}

// BstInsert 深度优先
// 插入左侧还是右
func (n *PNode[T]) BstInsert(root *PNode[T], val T) *PNode[T] {
	if root == nil {
		return &PNode[T]{Data: val}
	}
	if val < root.Data {
		root.Left = n.BstInsert(root.Left, val)
	}
	if val > root.Data {
		root.Right = n.BstInsert(root.Right, val)
	}
	return root
}
func (n *PNode[T]) BstBuild(val T, nodes []T) *PNode[T] {
	root := &PNode[T]{Data: val}
	for _, item := range nodes {
		n.BstInsert(root, item)
	}
	return root
}

/*
如果当前节点为空，则返回当前节点。
如果当前节点值大于val，则递归去左子树中搜索并删除，此时 root.left 也要跟着递归更新。
如果当前节点值小于val 则递归去右子树中搜索并删除，此时 root.right 也要跟着递归更新。
如果当前节点值等于val，则该节点就是待删除节点。

	如果当前节点的左子树为空，则删除该节点之后，则右子树代替当前节点位置，返回右子树。
	如果当前节点的右子树为空，则删除该节点之后，则左子树代替当前节点位置，返回左子树。
	如果当前节点的左右子树都有，则将左子树转移到右子树最左侧的叶子节点位置上，然后右子树代替当前节点位置
*/
func (n *PNode[T]) BstDel(root *PNode[T], val T) *PNode[T] {
	if root == nil {
		return root
	}
	switch val {
	case root.Data:
		if root.Left.IsEmpty() {
			return root.Right
		} else if root.Right.IsEmpty() {
			return root.Left
		} else {
			curr := root.Right
			for !curr.Left.IsEmpty() {
				curr = curr.Left
			}
			curr.Left = root.Left
			return root.Right
		}
	default:
		if cmp.Less(val, root.Data) {
			root.Left = n.BstDel(root.Left, val)
			return root
		} else {
			root.Right = n.BstDel(root.Right, val)
			return root
		}
	}
}
